Skip to main content

Reverse a Doubly Linked List

Problem​

Given a doubly linked list of n elements, the task is to reverse this list in-place.

Examples​

Example 1:

Input:
LinkedList: 3 <--> 4 <--> 5
Output:
5 4 3

Explanation:
After reversing the list, elements are 5 <--> 4 <--> 3.

Example 2:

Input:
LinkedList: 75 <--> 122 <--> 59 <--> 196
Output:
196 59 122 75

Explanation:
After reversing the list, elements are 196 <--> 59 <--> 122 <--> 75.

Your Task​

Your task is to complete the given function reverseDLL(), which takes head reference as an argument and reverses the elements in-place such that the tail becomes the new head and all pointers are pointing in the right order. You need to return the new head of the reversed list.

Expected Time Complexity: O(N)O(N)
Expected Auxiliary Space: O(1)O(1)

Constraints​

  • 1≤numberofnodes≤1041 ≤ number of nodes ≤ 10^4
  • 0≤valueofnodes≤1040 ≤ value of nodes ≤ 10^4

Solution​

Approach​

To reverse a doubly linked list in-place, we can use three pointers: previous_node, current_node, and next_node. The algorithm traverses the list, updating the pointers at each step until the entire list is reversed.

Python Code​

class Solution:
def reverseDLL(self, head):
while head:
head.next, head.prev = head.prev, head.next
if not head.prev:
return head
head = head.prev

Complexity Analysis​

  • Time Complexity: O(N),O(N), where N is the number of elements in the doubly linked list. We traverse the entire list once.
  • Space Complexity: O(1)O(1), as we only use a constant amount of extra space for pointers.

References​